class Solution
{
public:
    int openLock(vector<string> &deadends, string target)
    {
        unordered_set<string> visited(deadends.begin(), deadends.end());
        if (visited.count("0000"))
        {
            return -1;
        }
        if (target == "0000")
        {
            return 0;
        }
        queue<pair<string, int>> q;
        visited.insert("0000");
        q.push({"0000", 0});
        while (!q.empty())
        {
            auto [num, step] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                string adjacentNum = num;
                adjacentNum[i] = ((num[i] - '0' + 1) % 10) + '0';
                if (!visited.count(adjacentNum))
                {
                    if (adjacentNum == target)
                    {
                        return step + 1;
                    }
                    visited.insert(adjacentNum);
                    q.push({adjacentNum, step + 1});
                }
                adjacentNum[i] = ((num[i] - '0' + 9) % 10) + '0';
                if (!visited.count(adjacentNum))
                {
                    if (adjacentNum == target)
                    {
                        return step + 1;
                    }
                    visited.insert(adjacentNum);
                    q.push({adjacentNum, step + 1});
                }
            }
        }
        return -1;
    }
};